package org.lyc.dp;

/**
 * https://www.bilibili.com/video/BV1aa411f7uT?p=5&vd_source=65f5ad03ccd998407c9d802ca94f29fd
 * 爬楼梯的最小花费
 * 数组的每个下标作为一个阶梯, 第i个阶梯对应着一个非负数的体力花费值cost[i].
 * 每当爬上一个阶梯都要花费对应的体力值, 一旦支付了相应的体力值, 就可以选择向上爬1个或者2个台阶
 * 请找出到达楼层顶部的最小花费. 再开始时可以选择下标为0或1的元素作为起始元素
 * 输入 cost = [10,15,20]
 * 输出 15
 * 从cost[1]出发爬两个台阶
 * 输入 cost = [1,100,1,1,1,100,1,1,100,1]
 * 输出 6
 * 从cost[0]开始, cost[2],cost[4],cost[6],cost[7],cost[9]
 *
 * @author Liu Yicong
 * @date 2024/1/31
 */
public class CCostOfSteps {
	static int[] cost = {1, 100, 1, 1, 1, 100, 1, 1, 100, 1};
	static int length = cost.length;

	public static void main(String[] args) {
		int[] dp = new int[length + 1]; //dp[i] 表示爬到第i级的最小花费
		dp[0] = dp[1] = 0;
		for (int i = 2; i <= length; i++) {
			dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
		}
		System.out.println(dp[length]);
	}
}
